1. Field of the Invention
The present invention relates to a policing device for monitoring the bandwidth of packets flowing into a network.
2. Description of the Related Art
Along with an increase in the users of the Internet, the traffic flowing through the Internet is rapidly expanding. Since packets from many users share the same line on the Internet, the cost per bandwidth is lower than that in networks dedicated to specific groups of users. Because of this low cost, attempts are emerging to realize a reduction in communication cost by integrating telephone networks and enterprise networks through the Internet. The integration requires a bandwidth guarantee similar to what is available on conventional dedicated networks.
A description of the VBR□2 (Variable Bit Rate□2) service, which is an example of such bandwidth guarantee, is found in Chapter 4.5 of The ATM Forum Specification version 4.0 (hereinafter referred to as “Prior Art 1”). To use this service, each user contracts with a service provider for a sustainable cell rate (SCR) and a peak cell rate (PCR). The contracting user sets the cell loss priority (CLP) against discard in the cell header to priority (=“0”: hardly subject to discard) or non-priority (=“1”: more subject to discard) and transmits the cell. The policing function at the entrance to the network monitors the average bandwidth of cells whose CLP is “0” and either discards non-conformant cells or rewrites their CLP into “1”. It also monitors the maximum bandwidth of cells whose CLP is “0” or “1”, and discards non-conformant cells. As a node in the network discards cells of CLP=1 preferentially over cells of CLP=0 when in congestion, this network can guarantee an average bandwidth for cells whose CLP is “0”. Although the policing function of ATM is known as Usage Parameter Control (UPC), the terminology in the present application will be unified to “policing function”.
The Continuous State Leaky Bucket Algorithm (hereinafter referred as the leaky bucket algorithm) for policing function in ATM is stated in Chapter 4.4.2 of Prior Art 1. The leaky bucket algorithm is represented by a model of a holed bucket, therefore a leaky bucket having a certain capacity. As long as the bucket is holding water, a quantity of water leaks in proportion to the monitored bandwidth, and upon arrival of a cell a quantity of water equivalent to one cell is poured into the bucket. To allow for cell delay variations and bursts, input cells are judged as conformant until water overflows the bucket having a predetermined capacity, and when the bucket is overflowed, input cells are regarded as non-conformant.
A flow chart of the leaky bucket algorithm is shown in FIG. 17. When a cell arrives at time “ta” (step 1701), the time difference from the arrival time LCT of a cell judged as conformant last time (corresponding to the quantity of water leaking from the bucket) is calculated. The balance X′ of subtracting this value from a value of a counter X corresponding to the stored water quantity in the bucket is calculated (step 1702). If the balance X′ is negative, X′ will be corrected to “0” (step 1704). X′ is compared with a limit L corresponding to the capacity of the bucket (step 1705). If X′≧L holds, the input cell will be judged as non-conformant (step 1706). If X′<L holds, it will be judged as conformant, and a value resulting from the addition to X′ of a fixed value I corresponding to the quantity of water equivalent to one cell determined by the monitored bandwidth will be stored as a new value of X (step 1707). Incidentally, upon arrival of the first cell, X=0, LCT is initialized to the time of arrival of that cell.
A problem is known in the VBR.2 service of Prior Art 1 that the average bandwidth cannot be effectively utilized. The policing function according to Prior Art 1 subjects cells of CLP=0 to bandwidth monitoring, and transmits cells judged to be within the average bandwidth with their CLP being kept at 0. Even if the bandwidth of cell whose CLP is 0 drops below the average bandwidth, the policing function does not transmit any cell of CLP=1 as a cell of CLP=0. That is, the contracting user cannot use up all of the average bandwidth when cells of CLP=0 flow within the average bandwidth.
FIG. 16A shows an example of bandwidth variation of cells of CLP=0 and CLP=1 transmitted by the contracting user, wherein the shaded part represents CLP=0 and the blank part, CLP=1. FIG. 16B shows the bandwidth variation of each cell after passing through the policing function, wherein the hatched part represents CLP=0. Even though the cells of CLP=0 are within the average bandwidth at time period t0, the cell of CLP=1 is transmitted intact with CLP=1.
A policing function to solve this problem is proposed in the Japanese Laid-Open Patent No. 2000-349812 (hereinafter referred to as Prior Art 2). According to Prior Art 2, the contracting user and the service provider agree on a contract bandwidth, and the contracting user notifies the service provider of the method to distinguish important packets from other unimportant packets. The policing function of Prior Art 2 carries out bandwidth monitoring taking account of the relative importance of each received packet, and judges those packets found conformant to be priority packets and others to be non-priority packets. In this decision, if the bandwidth of the important packets is less than the contract bandwidth, unimportant packets will also be judged as priority packets. Therefore, when the total bandwidth of packets transmitted by the contracting user exceeds the contract bandwidth, the contracting user can exhaustively use the whole contract bandwidth.
Prior Art 2 further discloses a method to extend the leaky bucket algorithm so as to realize the bandwidth monitoring discussed above. The policing function according to Prior Art 2 uses an expanded leaky bucket algorithm applicable to variable-length packets. The algorithm uses a limit L-A for priority packets and a limit L-B for non-priority packets, and enables to treat unimportant packets also as priority packets when important packets are less than the monitored bandwidth, by setting L-A greater than L-B.
Prior Art 2 describes a fully prioritized allocation according to which the contract bandwidth promised to each contracting user is allocated to priority packets preferentially and, only when there is a surplus in the contract bandwidth, the bandwidth is also allocated to non-priority packets as well. According to Prior Art 2, if the bandwidth of important packets exceeds the contract bandwidth, none of unimportant packets will be judged as deserving priority. However, some of contracting users need to secure a minimum bandwidth for unimportant packets. For this reason, the policing device is required to flexibly allocate the contract bandwidth between important packets and unimportant packets.
So far, a case where one contracting user has a plurality of levels of importance has been considered, but there may be a case where one contracting user has a plurality of organizational units, such as departments for research and development, production, sales and so forth if the user is a business enterprise. In such a case, a bandwidth should be guaranteed not only for each contracting user but also for each department of the user. As the policing function according to Prior Art 2 allocates the contract bandwidth promised to each contracting user among its different departments in a fully prioritized way, some department may find no priority packet at its disposal. Nor does Prior Art 1 give any mention of a method to solve this problem.